/**
 * 208. 实现 Trie (前缀树)
 * https://leetcode-cn.com/problems/implement-trie-prefix-tree/
 */

const aCode = 'a'.charCodeAt(0);

/**
 * @param {string} val
 * @constructor
 */
function CharNode(val) {
  this.val = val;
  this.next = new Array(26);
}

function Trie() {
  this.root = new CharNode();
}

/**
 * @param {CharNode} node
 * @param {string} word
 * @param {number} index
 * @private
 */
function _insert(node, word, index) {
  if (index >= word.length) {
    node.val = word;
    return;
  }
  const nextNodeIndex = word.charCodeAt(index) - aCode;
  let nextNode = node.next[nextNodeIndex];
  if (!nextNode) {
    nextNode = new CharNode();
    node.next[nextNodeIndex] = nextNode;
  }
  _insert(nextNode, word, index + 1);
}

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function insert(word) {
  _insert(this.root, word, 0);
};

/**
 * @param {CharNode} node
 * @param {string} word
 * @param {number} index
 * @private
 */
function _search(node, word, index) {
  if (index >= word.length) return node.val === word;
  const nextNodeIndex = word.charCodeAt(index) - aCode;
  const nextNode = node.next[nextNodeIndex];
  if (!nextNode) {
    return false;
  }
  return _search(nextNode, word, index + 1);
}

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function search(word) {
  return _search(this.root, word, 0);
};

/**
 * @param {CharNode} node
 * @param {string} prefix
 * @param {number} index
 * @private
 */
function _startsWidth(node, prefix, index) {
  if (index >= prefix.length) return true;
  const nextNodeIndex = prefix.charCodeAt(index) - aCode;
  const nextNode = node.next[nextNodeIndex];
  if (!nextNode) {
    return false;
  }
  return _startsWidth(nextNode, prefix, index + 1);
}

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function startsWidth(prefix) {
  return _startsWidth(this.root, prefix, 0);
};

const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple') === true); // 返回 True
console.log(trie.search('app') === false); // 返回 False
console.log(trie.startsWith('app') === true); // 返回 True
trie.insert('app');
console.log(trie.search('app') === true); // 返回 True
